/****************************************************************************
 Copyright (c) 2017-2020 SuperSuRaccoon
 
 Site: http://www.supersuraccoon-cocos2d.com
 Mail: supersuraccoon@gmail.com

 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 THE SOFTWARE.
 ****************************************************************************/

var ssr = ssr || {};

ssr.PolyHelper = {};

ssr.PolyHelper.isConvex = function(verts) {
    if (verts.length < 4) {
        return true;
    }
    var sign = false;
    var n = verts.length;
    for(var i = 0; i < n; i++) {
        var dx1 = verts[(i + 2) % n].x - verts[(i + 1) % n].x;
        var dy1 = verts[(i + 2) % n].y - verts[(i + 1) % n].y;
        var dx2 = verts[i].x - verts[(i + 1) % n].x;
        var dy2 = verts[i].y - verts[(i + 1) % n].y;
        var zcrossproduct = dx1 * dy2 - dy1 * dx2;
        if (i == 0)
            sign = zcrossproduct > 0;
        else {
            if (sign != (zcrossproduct > 0))
                return false;
        }
    }
    return true;
}

ssr.PolyHelper.triangulateArea = function(poly) {
    var n = poly.length;
    var A = 0.0;
    for(var p = n-1, q = 0; q < n; p = q++) {
        A += poly[p].x * poly[q].y - poly[q].x * poly[p].y;
    }
    return A * 0.5;
};

ssr.PolyHelper.insideTriangle = function(Ax, Ay, Bx, By, Cx, Cy, Px, Py) {
    var ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
    var cCROSSap, bCROSScp, aCROSSbp;
    ax = Cx - Bx;  
    ay = Cy - By;
    bx = Ax - Cx;  
    by = Ay - Cy;
    cx = Bx - Ax;  
    cy = By - Ay;
    apx= Px - Ax;  
    apy= Py - Ay;
    bpx= Px - Bx;  
    bpy= Py - By;
    cpx= Px - Cx;  
    cpy= Py - Cy;
    aCROSSbp = ax * bpy - ay * bpx;
    cCROSSap = cx * apy - cy * apx;
    bCROSScp = bx * cpy - by * cpx;
    return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0));
};

ssr.PolyHelper.triangulateSnip = function(poly, u, v, w, n, V) {
    var p;
    var Ax, Ay, Bx, By, Cx, Cy, Px, Py;
    
    Ax = poly[V[u]].x;
    Ay = poly[V[u]].y;
    
    Bx = poly[V[v]].x;
    By = poly[V[v]].y;
    
    Cx = poly[V[w]].x;
    Cy = poly[V[w]].y;
    
    if (0.0000000001 > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax)))) {
        return false;
    }
    for (p = 0; p < n; p ++) {
        if((p == u) || (p == v) || (p == w)) {
            continue;
        }
        Px = poly[V[p]].x;
        Py = poly[V[p]].y;
        if (ssr.PolyHelper.insideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) {
            return false;
        }
    }
    return true;
};

ssr.PolyHelper.triangulate = function(poly) {
    var n = poly.length;
    var result = []; 
    if (n < 3) {
        return result;
    }
    var V = [];
    if (0.0 < ssr.PolyHelper.triangulateArea(poly)) {
        for (var v = 0; v < n; v ++) {
            V[v] = v;
        }
    }
    else {
        for(var v = 0; v < n; v ++) {
            V[v] = (n - 1) - v;
        }
    }
    var nv = n;
    var count = 2 * nv;
    for(var m = 0, v = nv - 1; nv > 2;) {
        if (0 >= (count--)) {
            return result;
        }
        var u = v; 
        if (nv <= u) {
            u = 0;
        }
        v = u + 1; 
        if (nv <= v) {
            v = 0;
        }
        var w = v + 1; 
        if (nv <= w) {
            w = 0;
        }
        if (ssr.PolyHelper.triangulateSnip(poly, u , v , w, nv, V)) {
            var a, b, c, s, t;
            a = V[u]; b = V[v]; c = V[w];
            result.push(poly[a]);
            result.push(poly[b]);
            result.push(poly[c]);
            m++;
            for(s = v,t = v + 1; t < nv; s ++, t ++) {
                V[s] = V[t]; 
            }
            nv --;
            count = 2 * nv;
        }
    }
    return result;
};

ssr.PolyHelper.isPointInPoly = function(pt, poly) {
    var i, j;
    var c = false;
    for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {
        if ((((poly[i].y <= pt.y) && (pt.y < poly[j].y)) ||
            ((poly[j].y <= pt.y) && (pt.y < poly[i].y)))
            && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y)/(poly[j].y - poly[i].y) + poly[i].x)) {
            c = !c;
        }
    }
    return c;
};

ssr.PolyHelper.intersectWithPoly = function(polygon1, polygon2) {
     if (polygon1.length <= 2 || polygon2.length <= 2) {
        return false;
    }
    // polygon1 : array[LinearRing,...]
    function intersectsByPolygon (polygon1, polygon2) {
        var intersect = false;

        intersect = intersectsByLinearRings(polygon1, polygon2);

        if(!intersect) {
            // check if this poly contains points of the ring/linestring
            for(i = 0, len = polygon2.length; i<len; ++i) {
                var point = polygon2[i];
                intersect = containsPointByLinearRing(point, polygon1);
                if(intersect) {
                    break;
                }
            }
        }
     
        return intersect;
    }

    // LinearRings
    function containsPointByPolygon (point, LinearRings) {
        var numRings = LinearRings.length;
        var contained = false;
        if(numRings > 0) {
            contained = containsPointByLinearRing(point, LinearRings[0]);
            if( numRings > 1) {
                // check interior rings
                var hole;
                for(var i=1; i<numRings; ++i) {
                    hole = containsPointByLinearRing(point, LinearRings[i]);
                    if(hole) {
                        if(hole === 1) {
                            // on edge
                            contained = 1;
                        } else {
                            // in hole
                            contained = false;
                        }                            
                        break;
                    }
                }
            }
        }
        return contained;
    }

    // LinearRing : array[pt]
    // point : {x:1,y:2}
    function containsPointByLinearRing (point, LinearRing) {

        //limitSigDigs
        function approx(num, sig) {
            var fig = 0;
            if (sig > 0) {
                fig = parseFloat(num.toPrecision(sig));
            }
            return fig;
        } 

        var digs = 14;
        var px = approx(point.x, digs);
        var py = approx(point.y, digs);
        function getX(y, x1, y1, x2, y2) {
            return (y - y2) * ((x2 - x1) / (y2 - y1)) + x2;
        }

        var numSeg = LinearRing.length - 1;
        var start, end, x1, y1, x2, y2, cx, cy;
        var crosses = 0;

        for(var i=0; i<numSeg; ++i) {
            start = LinearRing[i];
            x1 = approx(start.x, digs);
            y1 = approx(start.y, digs);
            end = LinearRing[i + 1];
            x2 = approx(end.x, digs);
            y2 = approx(end.y, digs);
            
            if(y1 == y2) {
                // horizontal edge
                if(py == y1) {
                    // point on horizontal line
                    if(x1 <= x2 && (px >= x1 && px <= x2) || // right or vert
                       x1 >= x2 && (px <= x1 && px >= x2)) { // left or vert
                        // point on edge
                        crosses = -1;
                        break;
                    }
                }
                // ignore other horizontal edges
                continue;
            }
            cx = approx(getX(py, x1, y1, x2, y2), digs);
            if(cx == px) {
                // point on line
                if(y1 < y2 && (py >= y1 && py <= y2) || // upward
                   y1 > y2 && (py <= y1 && py >= y2)) { // downward
                    // point on edge
                    crosses = -1;
                    break;
                }
            }
            if(cx <= px) {
                // no crossing to the right
                continue;
            }
            if(x1 != x2 && (cx < Math.min(x1, x2) || cx > Math.max(x1, x2))) {
                // no crossing
                continue;
            }
            if(y1 < y2 && (py >= y1 && py < y2) || // upward
               y1 > y2 && (py < y1 && py >= y2)) { // downward
                ++crosses;
            }
        }

        var contained = (crosses == -1) ?
            // on edge
            1 :
            // even (out) or odd (in)
            !!(crosses & 1);

        return contained;
    }

    function intersectsByLinearRings (LinearRing1, LinearRings2) {
        var intersect = false;
            var segs1 = getSortedSegments(LinearRing1); 
            var segs2 = getSortedSegments(LinearRings2); 
     
            var seg1, seg1x1, seg1x2, seg1y1, seg1y2,
                seg2, seg2y1, seg2y2;
            // sweep right
            outer: for(var i = 0, len = segs1.length; i < len; ++i) {
                seg1 = segs1[i];
                seg1x1 = seg1.x1;
                seg1x2 = seg1.x2;
                seg1y1 = seg1.y1;
                seg1y2 = seg1.y2;
                inner: for(var j = 0, jlen = segs2.length; j < jlen; ++j) {
                    seg2 = segs2[j];
                    if(seg2.x1 > seg1x2) {
                        // seg1 still left of seg2
                        break;
                    }
                    if(seg2.x2 < seg1x1) {
                        // seg2 still left of seg1
                        continue;
                    }
                    seg2y1 = seg2.y1;
                    seg2y2 = seg2.y2;
                    if(Math.min(seg2y1, seg2y2) > Math.max(seg1y1, seg1y2)) {
                        // seg2 above seg1
                        continue;
                    }
                    if(Math.max(seg2y1, seg2y2) < Math.min(seg1y1, seg1y2)) {
                        // seg2 below seg1
                        continue;
                    }
                    if(segmentsIntersect(seg1, seg2)) {
                        intersect = true;
                        break outer;
                    }
                }
            } 
        return intersect;
    }

    function getSortedSegments(points) {
        var numSeg = points.length - 1;
        var segments = new Array(numSeg), point1, point2;
        for(var i=0; i<numSeg; ++i) {
            point1 = points[i];
            point2 = points[i + 1];
            if(point1.x < point2.x) {
                segments[i] = {
                    x1: point1.x,
                    y1: point1.y,
                    x2: point2.x,
                    y2: point2.y
                };
            } else {
                segments[i] = {
                    x1: point2.x,
                    y1: point2.y,
                    x2: point1.x,
                    y2: point1.y
                };
            }
        }
        // more efficient to define this somewhere static
        function byX1(seg1, seg2) {
            return seg1.x1 - seg2.x1;
        }
        return segments.sort(byX1);
    }

    function segmentsIntersect(seg1, seg2, options) {
        var point = options && options.point;
        var tolerance = options && options.tolerance;
        var intersection = false;
        var x11_21 = seg1.x1 - seg2.x1;
        var y11_21 = seg1.y1 - seg2.y1;
        var x12_11 = seg1.x2 - seg1.x1;
        var y12_11 = seg1.y2 - seg1.y1;
        var y22_21 = seg2.y2 - seg2.y1;
        var x22_21 = seg2.x2 - seg2.x1;
        var d = (y22_21 * x12_11) - (x22_21 * y12_11);
        var n1 = (x22_21 * y11_21) - (y22_21 * x11_21);
        var n2 = (x12_11 * y11_21) - (y12_11 * x11_21);
        if(d == 0) {
            // parallel
            if(n1 == 0 && n2 == 0) {
                // coincident
                intersection = true;
            }
        } else {
            var along1 = n1 / d;
            var along2 = n2 / d;
            if(along1 >= 0 && along1 <= 1 && along2 >=0 && along2 <= 1) {
                // intersect
                if(!point) {
                    intersection = true;
                } else {
                    // calculate the intersection point
                    var x = seg1.x1 + (along1 * x12_11);
                    var y = seg1.y1 + (along1 * y12_11);
                    intersection = { 'x':x, 'y':y };
                }
            }
        }
        return intersection;
    };

    function distanceToSegment(point, segment) {
        var result = distanceSquaredToSegment(point, segment);
        result.distance = Math.sqrt(result.distance);
        return result;
    };

    function distanceSquaredToSegment(point, segment) {
        var x0 = point.x;
        var y0 = point.y;
        var x1 = segment.x1;
        var y1 = segment.y1;
        var x2 = segment.x2;
        var y2 = segment.y2;
        var dx = x2 - x1;
        var dy = y2 - y1;
        var along = ((dx * (x0 - x1)) + (dy * (y0 - y1))) /
                    (Math.pow(dx, 2) + Math.pow(dy, 2));
        var x, y;
        if(along <= 0.0) {
            x = x1;
            y = y1;
        } else if(along >= 1.0) {
            x = x2;
            y = y2;
        } else {
            x = x1 + along * dx;
            y = y1 + along * dy;
        }
        return {
            distance: Math.pow(x - x0, 2) + Math.pow(y - y0, 2),
            x: x, y: y,
            along: along
        };
    }

    //
    polygon1.push(polygon1[0]);
    polygon2.push(polygon2[0]);
    return intersectsByPolygon(polygon1, polygon2);
}

ssr.PolyHelper.intersectWithCircle = function(polygon, center, radius) {

    if (ll.Const.Global.IntersectionUseCpp) {
        result = js_cc_bridge.JS_CC_BRIDGE.getInstance().polygonAndCircle(
            polygon, center, parseInt(radius)
        );
        return result;
    }


    function pointInPolygon(point, polygon) {
        for (var n = polygon.length, i = 0, j = n - 1, x = point.x, y = point.y, inside = false; i < n; j = i++) {
            var xi = polygon[i].x, yi = polygon[i].y,
                xj = polygon[j].x, yj = polygon[j].y;
            if ((yi > y ^ yj > y) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi)) inside = !inside;
        }
        return inside;
    }

    function polygonEdges(polygon) {
        return polygon.map(function(p, i) {
            return i ? [polygon[i - 1], p] : [polygon[polygon.length - 1], p];
        });
    }

    function pointLineSegmentDistance(point, line) {
        var v = line[0], w = line[1];
        var d = pointPointSquaredDistance(v, w);
        if (d) {
            var t = ((point.x - v.x) * (w.x - v.x) + (point.y - v.y) * (w.y - v.y)) / d;
            if (t < 0) {
                d = v;
            }
            else {
                if (t > 1) {
                    d = w;
                }
                else {
                    d = cc.p(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y));
                }
            }
        }
        else {
            d = v;
        }
        return Math.sqrt(pointPointSquaredDistance(point, d));
    }

    function pointPointSquaredDistance(v, w) {
        var dx = v.x - w.x, dy = v.y - w.y;
        return dx * dx + dy * dy;
    }

    return pointInPolygon(center, polygon) || polygonEdges(polygon).some(
        function(line) {
            return pointLineSegmentDistance(center, line) < radius; 
        }
    )
};
